import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

/**
* @description: 剑指 Offer 59 - II. 队列的最大值
* @author hewei
* @date 2022/7/22 21:35
* @version 1.0
*/

public class MaxQueue {

    LinkedList<Integer> queue;
    List<Integer> list;
    int l;
    int r;

    public MaxQueue() {
        queue = new LinkedList<>();
        list = new ArrayList<>();
        l = -1;
        r = -1;
    }

    public int max_value() {
        return queue.isEmpty() ? -1 : list.get(queue.peek());
    }

    public void push_back(int value) {
        ++r;
        list.add(value);
        while (!queue.isEmpty() && list.get(queue.peekLast()) < value) queue.pollLast();
        queue.addLast(r);
    }

    public int pop_front() {
        if (queue.isEmpty()) return -1;
        Integer res = list.get(++l);
        if (queue.peekFirst() == l) queue.pollFirst();
        return res;
    }
}
